package sword;

/**
 * @Author: 海琳琦
 * @Date: 2022/5/26 22:12
 */
public class Title40 {

//    public static int[] getLeastNumbers(int[] arr, int k) {
//        //查找最小的k个数
//        int n = arr.length;
//        heapSort(arr, arr.length, k);
//        int[] result = new int[k];
//        int count = 0;
//        for (int i = n - 1; i >= n - k; i--) {
//            result[count++] = arr[i];
//        }
//        return result;
//    }
//
//    private static void heapSort(int[] arr, int n, int k) {
//        buildHeap(arr, n);
//        int count = 0;
//        while (n > 1 && count < k) {
//            count++;
//            swap(arr, 0, --n);
//            heapify(arr, 0, n);
//        }
//    }
//
//    private static void buildHeap(int[] arr, int n) {
//        for (int i = n / 2 - 1; i >= 0; i--) {
//            heapify(arr, i, n);
//        }
//    }
//
//    private static void heapify(int[] arr, int i, int n) {
//        int left = 2 * i + 1;
//        int right = 2 * i + 2;
//        int minIndex = i;
//        if (left < n && arr[left] < arr[minIndex]) {
//            minIndex = left;
//        }
//        if (right < n && arr[right] < arr[minIndex]) {
//            minIndex = right;
//        }
//        if (minIndex != i) {
//            swap(arr, i, minIndex);
//            heapify(arr, minIndex, n);
//        }
//    }
//
//    private static void swap(int[] arr, int i, int j) {
//        int temp = arr[i];
//        arr[i] = arr[j];
//        arr[j] = temp;
//    }

    public static int[] getLeastNumbers(int[] arr, int k) {
        int n = arr.length;
        heapSort(arr, n, k);
        int[] result = new int[k];
        int count = 0;
        for (int i = n - 1; i >= n - k; i--) {
            result[count++] = arr[i];
        }
        return result;
    }

    private static void heapSort(int[] arr, int n, int k) {
        buildHeap(arr, n);
        while (n > 1 && k-- > 0) {
            swap(arr, 0, --n);
            heapify(arr, 0, n);
        }
    }

    private static void buildHeap(int[] arr, int n) {
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, i, n);
        }
    }

    private static void heapify(int[] arr, int i, int n) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int minIndex = i;
        if (left < n && arr[left] < arr[minIndex]) {
            minIndex = left;
        }
        if (right < n && arr[right] < arr[minIndex]) {
            minIndex = right;
        }
        if (minIndex != i) {
            swap(arr, i, minIndex);
            heapify(arr, minIndex, n);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }




    public static void main(String[] args) {
        int[] arr = {3,2,1};
        int k = 2;
        getLeastNumbers(arr, k);
    }
}
